<!DOCTYPE html>
<html lang="en">

<head>
    <meta charset="UTF-8">
    <meta http-equiv="X-UA-Compatible" content="IE=edge">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>实现哈希表</title>
</head>

<body>
    <script>
        class HashTable {
            //实际保存数据的地方,用链表法解决冲突,所以storage的大概结构为:[[[key,val],[key,val]],[[key,val]]]
            storage = [];
            //哈希表中已保存的哈希项
            count = 0;
            //哈希表的总长度,这个长度可以自动变换的
            limit = 7;

            //哈希函数:str:字符数据,size:哈希表总长度(limit)
            hashFunc(str, size) {
                let hashFunc = 0;
                for (let i = 0; i < str.length; i++) {
                    //有一个尽量不会重复的hashFunc值
                    hashFunc = 37 * hashFunc + str.charCodeAt(i);
                }
                //取模后,下标值范围在0-size之间,最大不会等于size
                return hashFunc % size;
            }

            //put():插入和修改函数是同一个,因为在哈希表中,有则是修改,无则为插入
            /*实现步骤:
                1.根据key获取索引值 
                2.根据索引值获取桶(bucket)
                    2.1 如果桶不存在,则创建,并且防止该索引的位置
                3.判断是新增还是修改值
                    3.1如果有值则修改,没有值就插入
            */
            //达到目的:将数据插入到数组中
            put(key, val) {
                //获取hashCode,也可以说是storage数组的下标
                let index = this.hashFunc(key, this.limit);
                //console.log(index);
                //bucket是因为这个哈希表的设计是选择链地址法解决冲突才有bucket这个数组,这个数组中存着一个个hashCode重复的数据
                let bucket = this.storage[index];
                //如果这个位置还么有值,则需要创建
                if (bucket == null) {
                    bucket = [];
                    //把创建好的桶添加进哈希表
                    this.storage[index] = bucket;
                }

                for (let i = 0; i < bucket.length; i++) {
                    //里面有相同的key则表示需要修改
                    if (bucket[i][0] === key) {
                        bucket[i][1] = val
                        //修改完后就结束方法
                        return;
                    }
                }

                //如果不是修改,那么就执行插入
                bucket.push([key, val])
                //哈希表的长度加一
                this.count += 1;

                //判断是否需要扩容
                if(this.count > this.limit * 0.75){
                    const newLimit = this.getPrime(this.limit * 2);
                    this.resize(newLimit);
                }
            }

            //get(key)
            /*实现步骤:
                1.根据key获取索引值 
                2.根据索引值获取桶(bucket)
                3.如果桶为null,则直接返回-1,表示查找不到
                4.否则遍历桶,同时从桶中取出[key,val]数据,将取出的key与传入的key对比,有则返回,无则返回-1
            */
            get(key) {
                const index = this.hashFunc(key, this.limit);
                let bucket = this.storage[index];
                if (bucket == null) return -1;
                for (let i = 0; i < bucket.length; i++) {
                    if (bucket[i][0] === key) {
                        //把查找到的值返回出去
                        return bucket[i][1];
                    }
                }
                //桶里面也么有
                return -1;
            }

            /*remove(key):实现思路:
                1.根据key获取索引值 
                2.根据索引值获取桶(bucket)
                3.如果桶为null则返回删除元素不存在
                4.否则遍历桶,将key相等的项删除,没有相等的就表示删除的元素不存在              
            */
            remove(key) {
                const index = this.hashFunc(key, this.limit);
                let bucket = this.storage[index];
                if (bucket == null) return null;
                for (let i = 0; i < bucket.length; i++) {
                    if (bucket[i][0] === key) {
                        const val = bucket[i][1];
                        //将对应下标的桶值删除
                        bucket.splice(i, 1);
                        this.count -= 1;

                        //判断是否需要缩容
                        if(this.limit > 7 && this.count < this.limit * 0.25){
                            const newLimit = this.getPrime(Math.floor(this.limit / 2))
                            this.resize(newLimit);
                        }

                        //把删掉的值返回出去
                        return val;
                    }

                }
                //桶里面也么有
                return null;
            }

            //isEmpty():判断哈希表是否为空
            isEmpty() {
                return this.count === 0 ? true : false;
            }

            //size():返回哈希表中元素的个数
            size() {
                return this.count;
            }

            //判断是否为质数
            isPrime(num) {
                let sqrtNum = parseInt(Math.sqrt(num));
                for (let i = 2; i <= sqrtNum; i++) {
                    if (num % i == 0) {
                        return false;
                    }
                }
                return true;
            }
            //查找质数,保证返回一个恒为质数的数
            getPrime(num){
                while(!this.isPrime(num)){
                    num++;
                }
                return num;
            }

            //哈希表扩容方法
            resize(newLimit){
                //1.保存旧的数组的值
                let ordStorage = this.storage;

                //2.重置所有的属性
                this.storage = [];
                this.limit = newLimit; //将新的容量赋给它
                this.count = 0;

                //3.遍历旧表中的所有的桶(bucket)
                ordStorage.forEach(bucket => {
                    //判断bucket是否为空
                    if(bucket === null) continue;

                    //不为空则取出里面的值,重新添加到新的storage中
                    bucket.forEach(item=>{
                        this.put(item[0],item[1])
                    })
                });
            }

        }

        //哈希表测试代码
        let ht = new HashTable();
        //测试添加
        ht.put('abc', '111');
        ht.put('bad', '222');
        ht.put('cdd', '333');
        console.log(ht.storage);

        //测试修改
        /* ht.put('aaa','444')
        console.log(ht.storage); */

        //测试删除
        console.log(ht.remove('cdd'));
        console.log(ht.storage);
    </script>
</body>

</html>